package com.zx._12_算法.剑指offer._2022;

import java.util.HashSet;

/**
 * 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
 *
 * https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/
 */
public class 顺时针打印矩阵 {

    // 顺时针4个方向, x ,y
    int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public static void main(String[] args) {
        int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        int[] ints = new 顺时针打印矩阵().spiralOrder(matrix);
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }

    public int[] spiralOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return new int[0];
        }
        int[] res = new int[matrix.length * matrix[0].length];
        // 遇到边界就转90度，并且不走走过的
        HashSet<String> counter = new HashSet<>();

        // 顺时针4个方向, x ,y
        int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        // 初始化的方向
        int initDir = 0;

        int resIdx = 0;

        int x = 0;
        int y = 0;
        while (true) {
            // 都走完了
            if (counter.size() == res.length) {
                break;
            }
            // 获得记录，保存位置
            res[resIdx] = matrix[x][y];
            resIdx++;
            counter.add(x + ":" + y);

            // 移动位置
            int newX = x + dir[initDir][0];
            int newY = y + dir[initDir][1];
            // 判断是否到达边界&已经重复
            boolean change = (newX < 0 || newX >= matrix.length) ||
                    (newY < 0 || newY >= matrix[0].length) ||
                    counter.contains(newX + ":" + newY);
            if (change) {
                initDir = (initDir + 1) % 4;
                newX = x + dir[initDir][0];
                newY = y + dir[initDir][1];
            }

            x = newX;
            y = newY;
        }

        return res;
    }

}
